package com.yang.Dp.bags.ComBages;

/**
 * @Author: yang
 * @Description: 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数
 * 题目数据保证答案符合 32 位整数范围
 * @Date: Created in 16:39 2022/8/11
 * @Modified By:
 */
public class LeetCode377 {
}

class LeetCode377Solution {
    public int combinationSum4(int[] nums, int target) {
        // 1.dp[j] 表示 容量i装满 有多少种组合
        // 2.递推公式： dp[j] += dp[j - nums[i]];
        // 3.初始化 dp[0] = 1
        // 4.循环方式 因为顺序不同的序列被视作不同的组合 所以 这可以算作是排列
        int dp[] = new int[target + 1];
        dp[0] = 1;

        // 排列先循环容量 后循环物品
        for(int i = 0; i <= target; i++){
            for(int j = 0; j < nums.length; j++){
                if(i >= nums[j]){
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
}
